package pro.softzhang.algo.lc1900;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 1926. 迷宫中离入口最近的出口
 * https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze
 */
public class LC1926_NearestExitFromEntranceInMaze {
    public static void main(String[] args) {

    }

    static
    class Solution {
        private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        /**
         * @param maze
         * @param entrance
         * @return
         */
        public int nearestExit(char[][] maze, int[] entrance) {
            int m = maze.length, n = maze[0].length;

            boolean[][] visited = new boolean[m][n];
            visited[entrance[0]][entrance[1]] = true;

            Queue<int[]> queue = new ArrayDeque<>();
            queue.offer(entrance);

            int steps = 0;
            while (!queue.isEmpty()) {
                steps++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] cell = queue.poll();
                    int row = cell[0], col = cell[1];
                    for (int[] dir : dirs) {
                        int newRow = row + dir[0], newCol = col + dir[1];
                        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol] && maze[newRow][newCol] == '.') {
                            if (newRow == 0 || newRow == m - 1 || newCol == 0 || newCol == n - 1) {
                                return steps;
                            }
                            visited[newRow][newCol] = true;
                            queue.offer(new int[]{newRow, newCol});
                        }
                    }
                }
            }
            return -1;
        }
    }
}
